Make array strictly increasing

Time: O(N^2xLogN); Space: O(N); hard

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]

Output: 1

Explanation:

  • Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]

Output: 2

Explanation:

  • Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]

Output: -1

Explanation:

  • You can’t make arr1 strictly increasing.

Constraints:

  • 1 <= len(arr1), len(arr2) <= 2000

  • 0 <= arr1[i], arr2[i] <= 10^9

Hints:

  1. Use dynamic programming.

  2. The state would be the index in arr1 and the index of the previous element in arr2 after sorting it and removing duplicates.

1. Dynamic programming [O(N^2*LogN), O(N)]

[5]:

import collections
import bisect

class Solution1(object):
    """
    Time: O(N^2*LogN)
    Space: O(N)
    """
    def makeArrayIncreasing(self, arr1, arr2):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :rtype: int
        """
        arr2 = sorted(set(arr2))
        dp = {0: -1}                          # dp[min_cost] = end_with_val

        for val1 in arr1:
            next_dp = collections.defaultdict(lambda: float("inf"))
            for cost, val in dp.items():
                if val < val1:
                    next_dp[cost] = min(next_dp[cost], val1)
                k = bisect.bisect_right(arr2, val)
                if k == len(arr2):
                    continue
                next_dp[cost+1] = min(next_dp[cost+1], arr2[k])

            dp = next_dp

            if not dp:
                return -1

        return min(dp.keys())

[6]:

s = Solution1()

arr1 = [1,5,3,6,7]
arr2 = [1,3,2,4]
assert s.makeArrayIncreasing(arr1, arr2) == 1

arr1 = [1,5,3,6,7]
arr2 = [4,3,1]
assert s.makeArrayIncreasing(arr1, arr2) == 2

arr1 = [1,5,3,6,7]
arr2 = [1,6,3,3]
assert s.makeArrayIncreasing(arr1, arr2) == -1